package com.camus.algorithm.impl;

import com.camus.algorithm.SubsetAlgorithm4Int;

/**
 * 滑动窗口算法求目标和的子集
 * 
 * @author jie.deng
 *
 */
public class SubsetAlgorithmOfSlideWindow4IntEg implements SubsetAlgorithm4Int {

	@Override
	public int[] findSubsetOfTargetSum(int[] candidateArr, int target) {
		// 算法复杂度为O(n*n)，可能找不到结果
		int[] subsetArr = null;
		int len = candidateArr.length;

		// 前缀和
		int[] prefixSumArr = new int[len];
		prefixSumArr[0] = candidateArr[0];
		for (int i = 1; i < len; i++) {
			prefixSumArr[i] = prefixSumArr[i - 1] + candidateArr[i];
		}

		// 滑动窗口大小为2...len
		loop: for (int winSize = 2; winSize <= len; winSize++) {
			// 区间和[i,j] = prefixSum[j] - prefixSum[i-1]
			for (int startIdx = 0, endIdx = startIdx + winSize - 1; endIdx < len; startIdx++, endIdx++) {
				// 求区间和[startIdx,endIdx]
				int sum = prefixSumArr[endIdx];
				if (startIdx > 0) {
					sum = sum - prefixSumArr[startIdx - 1];
				}
				if (sum == target) {
					subsetArr = new int[winSize];
					for (int i = 0; i < winSize; i++) {
						subsetArr[i] = candidateArr[i + startIdx];
					}
					break loop;
				}
			}
		}
		return subsetArr;
	}

}
